#ifndef NODE_H
#define NODE_H

#include "pattern.h"
#include <vector>
#include <stack>
#include <string>

#include <iostream>
using namespace std;
#include <cassert>
using std::string;
class Pattern;
struct Node{
    Node(Pattern* p);
    ~Node(){}

    virtual bool match(Matcher* m,size_t from,const string& text)=0;

    Pattern* p;
    Node* next;   
};

//terminal
struct Accept: public Node{
    Accept(Pattern* p)
        :Node(p)
    {
        next = 0;
    }

    bool match(Matcher*,size_t,const string&){
        return true;
    }
};

//atom nodes
struct Literal : public Node{
    Literal(Pattern* p,char _c)
        :Node(p)
    {
        c = _c;
    }
    bool match(Matcher *m, size_t from, const string &text){
        if(from==text.length() || text[from]!=c)
            return false;
        m->setLastMatchTo(from);
        return  next->match(m,from+1,text);
    }

    char c;

};

struct IgnoreCaseLiteral : public Node {
    IgnoreCaseLiteral(Pattern* p,char _c)
        :Node(p)
    {
        c = _c;
    }
    bool match(Matcher *m, size_t from, const string &text){
        if(from==text.length() || (tolower(text[from])!=c && toupper(text[from])!=c))
            return false;
        m->setLastMatchTo(from);
        return  next->match(m,from+1,text);
    }
    char c;
};

struct LiteralSequence : public Node{
    LiteralSequence(Pattern* p)
        :Node(p)
    {

    }
    void append(char c){
        seq.push_back(c);
    }
    bool match(Matcher* m, size_t from,const string& text){
        for(size_t i=0;i<seq.size();++i){
            if(from + i>=text.length() ||
                    seq[i] != text[from+i]){
                return false;
            }            
        }
        m->setLastMatchTo(from+seq.size()-1);

        return next->match(m,from+seq.size(),text);
    }

    std::string seq;
};

struct Dot : public Node{
    Dot(Pattern* p)
        :Node(p)
    {}
    bool match(Matcher* m, size_t from, const string &text){
        if(from >= text.length())
            return false;
        if(text[from] != '\n' && text[from] != '\r'){
            m->setLastMatchTo(from);
            return next->match(m,from+1,text);
        } else if(text[from]=='\r' && text[from+1]!='\n'){
            m->setLastMatchTo(from+1);
            return next->match(m,from+2,text);
        }
        return false;
    }
};
struct DotAll : public Node{
    DotAll(Pattern* p)
        :Node(p)
    {}
    bool match(Matcher *m, size_t from, const string &text){
        m->setLastMatchTo(from+1);
        return next->match(m,from+1,text);
    }
};
struct StringBegin : public Node{
    StringBegin(Pattern* p)
        :Node(p){}
    bool match(Matcher *m, size_t from, const string &text){
        return from==0 && next->match(m,from,text);
    }
};
struct StringEnd: public Node{
    StringEnd(Pattern* p)
        :Node(p){}
    bool match(Matcher *m, size_t from, const string &text){
        return from==text.length()-1 && next->match(m,from,text);
    }
};

struct LineBegin : public Node{
    LineBegin(Pattern* p)
        :Node(p)
    {}
    bool match(Matcher *m, size_t from, const string &text){
        if(from==0)
            return next->match(m,0,text);
        if(from>=text.length())
            return false;
        return (text[from-1]=='\n') && next->match(m,from,text);
    }
};

struct LineEnd : public Node{
    LineEnd(Pattern* p)
        :Node(p)
    {}
    bool match(Matcher *m, size_t from, const string &text){
        return (text[from]=='\n' || (text[from]=='\r' && text[from]=='\n'))
                && next->match(m,from,text);
    }
};

struct Boundary : public Node{
    Boundary(Pattern* p)
        :Node(p){}
    bool match(Matcher *m, size_t from, const string &text){
        return check(from,text) && next->match(m,from,text);
    }

    bool check(size_t from,const string& text){
        if(from==0)
            return isAlphanumeric(text[0]);

        if(from==text.length())
            return isAlphanumeric(text[from-1]);

        if(isAlphanumeric(text[from]))
            return !isAlphanumeric(text[from-1]);
        else
            return isAlphanumeric(text[from+1]);
    }

    bool isAlphanumeric(char c){
        return isdigit(c) || isalpha(c);
    }
};

//complex nodes
struct Alternative: public Node{
    Alternative(Pattern* p,Node* a,Node* b)
        :Node(p)
    {
        appendChoice(a);
        appendChoice(b);
    }
    void appendChoice(Node* choice){
        choices.push_back(choice);
    }
    bool match(Matcher* m, size_t from,const string& text){
        for(size_t i=0;i<choices.size();++i){
            if(choices[i]->match(m,from,text)){
                return true;
            }            
        }
        return false;
    }

    std::vector<Node*> choices;
};

//repetition related
struct Que : public Node{
    Que(Pattern* p,Node* _atom,bool _greedy=true)
        :Node(p)
    {
        atom = _atom;
        greedy = _greedy;
    }

    bool match(Matcher *m, size_t from, const string &text){
        if(greedy){            
            return (atom->match(m,from,text) && next->match(m,m->getLastMatchTo()+1,text)) ||
                    next->match(m,from,text);
        } else {
            return next->match(m,from,text) ||
                    (atom->match(m,from,text) && next->match(m,m->getLastMatchTo()+1,text));
        }
    }

    Node* atom;
    bool greedy;
};

struct Repetition : public Node{
    Repetition(Pattern* p,Node* _atom,int _min,int _max,bool _greedy=true)
        :Node(p)
    {
        atom = _atom;
        min = _min;
        max = _max;
        greedy = _greedy;
    }

    bool match(Matcher *m, size_t from, const string &text){
        if(max<min)
            return false;
        int count = 0;
        int cur_from = from;
        while(count < min){
            if(!atom->match(m,cur_from,text))
                return false;
            cur_from = m->getLastMatchTo()+1;
            ++count;
        }
        if(greedy){
            std::stack<int> back_trace;
            back_trace.push(cur_from);
            while(count < max){
                if(atom->match(m,cur_from,text)){
                    cur_from = m->getLastMatchTo()+1;
                    back_trace.push(cur_from);
                    ++count;
                } else {
                    break;
                }
            }
            while(!back_trace.empty()){
                cur_from = back_trace.top();
                back_trace.pop();
                if(next->match(m,cur_from,text))
                    return true;
            }
            return false;
        } else {
            //reluctent
            if(next->match(m,cur_from,text))
                return true;
            while(count<max){
                if(atom->match(m,cur_from,text)){
                    cur_from = m->getLastMatchTo()+1;
                    if(next->match(m,cur_from,text))
                        return true;
                    ++count;
                } else {
                    break;
                }
            }
            return false;
        }
    }

    int min,max;
    bool greedy;
    Node* atom;
};

//group related
struct Group;

//mark end of group match and handle backtrace
struct GroupTail : public Node{
    GroupTail(Pattern* p,Group* _g)
        :Node(p)
    {
        g = _g;
    }
    bool match(Matcher *m, size_t from, const string &text);

    Group* g;
};

struct Group : public Node{
    Group(Pattern* p,Node* _body,bool _capture,int _index=-1,const std::string& _name="")
        :Node(p)
    {
        capture = _capture;
        body = _body;
        group_index = _index;
        if(!_name.empty()){
            p->addName(_name,group_index);
        }

        tail = new GroupTail(p,this);

        //find tail
        Node* cur = body;
        Node* prev = 0;
        while(cur != p->getAcceptNode()){
            prev = cur;
            cur = cur->next;
        }
        prev->next = tail;

    }

    bool match(Matcher *m, size_t from, const string &text){
        int save_last_from = m->capture_groups[group_index].from;
        markFrom(m,from);
        if(body->match(m,from,text)){            
            return true;
        }
        else{            
            markFrom(m,save_last_from);
            return false;
        }
    }

    void markFrom(Matcher* m,int from){
        if(capture && group_index>0){
            m->capture_groups[group_index].from = from;
        }
    }
    void markTo(Matcher* m,int to){
        if(capture && group_index>0){
            m->capture_groups[group_index].to = to;
        }
    }

    Node* body;
    GroupTail* tail;
    bool capture;
    int group_index;
};

//backref
struct GroupRef : public Node{
    GroupRef(Pattern* p,int _ref_index)
        :Node(p)
    {
        ref_index = _ref_index;
    }
    GroupRef(Pattern *p, const string& _ref_name)
        :Node(p)
    {
        ref_index = p->getIndexByName(_ref_name);
    }

    bool match(Matcher *m, size_t from, const string &text){
        string ref_text = m->group(ref_index);
        for(size_t i = 0;i<ref_text.length();++i){
            if(ref_text[i] != text[from+i])
                return false;
        }

        m->setLastMatchTo(from+ref_text.length()-1);
        return next->match(m,from+ref_text.length(),text);
    }

    int ref_index;
};

struct PosLookahead : public Node{
    PosLookahead(Pattern* p,Node* _body)
        :Node(p)
    {
        body = _body;
    }
    bool match(Matcher *m, size_t from, const string &text){
        int last_match_to_save = m->getLastMatchTo();
        if(body->match(m,from,text)){
            m->setLastMatchTo(last_match_to_save);
            return next->match(m,from,text);
        }
        return false;
    }

    Node* body;
};

struct NegLookahead : public Node{
    NegLookahead(Pattern* p,Node* _body)
        :Node(p)
    {
        body = _body;
    }
    bool match(Matcher *m, size_t from, const string &text){
        if(body->match(m,from,text)){
           return false;
        }
        return next->match(m,from,text);
    }

    Node* body;
};

struct YesNoBranch : public Node{
    YesNoBranch(Pattern* p,int _ref_group_index,Node* _yes,Node* _no)
        :Node(p)
    {
        ref_group_index = _ref_group_index;
        yes = _yes;
        no = _no;
    }
    bool match(Matcher *m, size_t from, const string &text){
        if(m->group(ref_group_index).empty()){
            return no->match(m,from,text);
        }
        else{
            cout<<"yes"<<endl;
            return yes->match(m,from,text);
        }
    }

    int ref_group_index;
    Node* yes;
    Node* no;
};

/*
class LookbehindAssertion : public Node{
    LookbehindAssertion(Pattern* p,Node* _atom)
        :Node(p)
    {

    }
    Node* atom;
};

*/
#endif // NODE_H
